/*
Manacher算法应用，在一个字符串末尾添加字符，使得字符串整体回文
 */

/**
 * 生成manacher字符串
 * @param str
 * @private
 * @return {string[]}
 */
function _manacherString (str) {
  const res = []
  for (let i = 0; i < str.length; i++) {
    res.push('#')
    res.push(str.charAt(i))
  }
  res.push('#')
  return res
}

/**
 * 获取要添加的字符串
 * @param {string} str
 */
function makeStr (str) {
  const chars = _manacherString(str)
  const radius = new Array(chars.length)
  let R = -1
  let C = -1
  let maxContainsIndex = -1
  for (let i = 0; i < chars.length; i++) {
    radius[i] = R > i ? Math.min(radius[2 * C - i], R - i + 1) : 1
    while (i + radius[i] < chars.length && i - radius[i] > -1) {
      if (chars[i + radius[i]] === chars[i - radius[i]]) {
        radius[i]++
      } else {
        break
      }
    }
    if (i + radius[i] > R) {
      R = i + radius[i] - 1
      C = i
    }
    if (R === chars.length - 1) {
      maxContainsIndex = radius[i] // 在manacherString里面radius是回文半径(包含当前位置)，在原字符串里面，就是回文直径+1
      break
    }
  }
  const res = new Array(str.length - maxContainsIndex + 1)
  for (let i = 0; i < res.length; i++) {
    res[res.length - 1 - i] = chars[2 * i + 1]
  }
  return res.join('')
}

console.log('abcd123321' + makeStr('abcd123321'))
